import java.util.*;

/**
 * 二叉树工具类
 */
public class MyTreeNodeUtils {
    /**
     * 二叉树对象序列化为字符串
     * 生成字符串格式：[1 2 3 # # 4 5]
     * # 表示 null 节点，节点与节点之间用 ' ' 分隔
     */
    public static String serialize(TreeNode root) {
        if (root == null) {
            // 没有节点的情况
            return "[]";
        }
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            // 添加节点前，先添加个空格分隔符
            sb.append(' ');
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append('#');
                continue;
            }
            sb.append(node.val);
            // 左右子节点入队
            queue.add(node.left);
            queue.add(node.right);
        }
        // 截取，排除首字符上的空格
        return '[' + sb.substring(1) + ']';
    }

    /**
     * 字符串反序列化为二叉树对象
     * 解析字符串格式：[1 2 3 # # 4 5]
     * # 表示 null 节点，节点与节点之间用 ' ' 分隔
     */
    private static int index;
    public static TreeNode deserialize(String data) {
        index = 0;
        if (data.length() < 3) {
            // "[]" 的情况时，反序列化为 null
            return null;
        }
        // 截取括号里的子串
        data = data.substring(1, data.length() - 1);
        char[] arr = data.toCharArray();
        int val = calcNum(arr);
        index++;

        TreeNode root = new TreeNode(val);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (index < arr.length) {
            TreeNode parents = queue.poll();
            // 后面的两个元素，就是其左右子节点
            if (arr[index] != '#') {
                // 左子节点不为 null 时，创建节点并入队
                val = calcNum(arr);
                parents.left = new TreeNode(val);
                queue.add(parents.left);
            } else {
                // 为 '#' 时，后移一位，即移出 '#' 位置
                index ++;
            }
            // 移出 ' ' 空格分隔位置
            index ++;
            // 判断 parents 节点是否存在右子节点，且右子节点不为 null
            if (index < arr.length && arr[index] != '#') {
                // 右子节点不为 null 时，创建节点并入队
                val = calcNum(arr);
                parents.right = new TreeNode(val);
                queue.add(parents.right);
            } else {
                // 为 '#' 时，后移一位，即移出 '#' 位置
                index ++;
            }
            // 移出 ' ' 空格分隔位置
            index ++;
        }
        return root;
    }

    /**
     * 计算连续数字字符组成的数字，遇到空格即停止循环
     */
    private static int calcNum(char[] arr) {
        int flag = 1, val = 0;
        if (arr[index] == '-') {
            flag = -1;
            ++ index;
        }
        while (index < arr.length && arr[index] != ' ') {
            val = val * 10 + (arr[index] - '0');
            index ++;
        }
        return flag * val;
    }

    /**
     * 获取 root 的深度
     * 根节点深度为 1
     */
    public static int getDeep(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDeep = getDeep(root.left);
        int rightDeep = getDeep(root.right);
        return Math.max(leftDeep, rightDeep) + 1;
    }

    /**
     * 返回值为 val 的节点
     * 节点值唯一
     */
    public static TreeNode getNode(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        TreeNode leftRes = getNode(root.left, val);
        TreeNode rightRes = getNode(root.right, val);
        if (leftRes != null) {
            return leftRes;
        }
        if (rightRes != null) {
            return rightRes;
        }
        return null;
    }
}
